Liste doublement chainée¶

Principe¶

La liste doublement chainée étend le concept de liste en ajoutant un lien vers l'élément précédent à chaque maillon de la chaine.

In [1]:

class Maillon:
    def __init__(self, v, s = None, p = None):
        self.donnee = v
        self.suivant = s 
        self.precedent = p 

        if s: s.precedent = self 
        if p: p.suivant = self
            
    def __str__(self): 
        return "{}".format(self.donnee)

Les arguments optionnels s et p permettent de spécifier à la construction les éléments suivants et précédents.

Comme pour la liste simple, nous écrivons une classe Liste qui a pour attributs la tête et la queue de la liste, plus éventuellement la taille. On pourrait l'écrire

In [3]:

class Liste:
    def __init__(self):
        self.tete = None
        self.queue = None
        self.N = 0

Mais comme pour la liste simple, on a avantage à utiliser des maillons vides aux extrémités. Il en suffit d'un que l'on appelle ici __tq. Dès lors,

l'élément de tête est __tq.suivant
l'élément de queue est __tq.precedent

Dans une liste vide, __tq.suivant = __tq.precedent = __tq.

In [4]:

class MaillonVide:
    def __init__(self):
        self.suivant = self
        self.precedent = self
        
class Liste:
    def __init__(self):
        self.__tq = MaillonVide()
        self.__N = 0
        
    __str__ = __liste_double_str__

Itérateur¶

Avant toute chose, écrivons la classe d'itération.

Elle est similaire à celle de forward_list, mais y ajoute les méthodes

decr
precedent

permettant de passer au maillon précédent.

In [5]:

class list_iterator:
    def __init__(self,maillon): self.__M = maillon
        
    def __str__(self): return self.__M.__str__()

    def copie(self):   return list_iterator(self.__M)
    
    def incr(self):    self.__M = self.__M.suivant
        
    def decr(self):    self.__M = self.__M.precedent
    
    def suivant(self, N = 1): 
        s = self.copie()
        for i in range(N): s.incr()
        return s
    
    def precedent(self, N = 1): 
        s = self.copie() 
        for i in range(N): s.decr()
        return s
        
    def get_val(self): return self.__M.donnee
    
    def set_val(self,val): self.__M.donnee = val
        
    def __eq__(self,other):
        return isinstance(other,list_iterator) \
               and self.__M == other.__M

Et ajoutons les méthodes begin() et end() à la classe Liste

In [6]:

def liste_begin(L): return list_iterator(L._Liste__tq.suivant)

Liste.begin = liste_begin

In [7]:

def liste_end(L):  return list_iterator(L._Liste__tq)

Liste.end = liste_end

Par rapport à une liste simplement chainée, notons que end() retourne un itérateur qui pointe vers le maillon vide __tq et pas un lien nul.

Opérations¶

Les opérations essentielles sont

indiquer la taille, indiquer si la liste est vide
insérer et supprimer en position quelconque
insérer et supprimer en tête
insérer et supprimer en queue
traverser et itérer en avant ou en arrière

Taille et vide¶

Une liste est vide si L.begin() et L.end() sont identiques (L.end() n'est pas inclus dans la liste)

In [8]:

def est_vide(L):
    return L.begin() == L.end()
Liste.empty = est_vide

Retourner la taille d'une liste requiert en général de parcourir toute la liste pour compter les maillons, une opération $\Theta(n)$

Ici on a choisi de stocker et maintenir cet information comme attribut de Liste

In [9]:

def taille(L):
    return L._Liste__N 
Liste.size = taille

Insertion avant un maillon `M`¶

créer un nouveau maillon N
relier N à gauche au maillon précédent M
- N.precedent = M.precedent
- M.precedent.suivant = N
relier N à droite à M
- N.suivant = M
- M.precedent = N

In [10]:

def inserer_avant(M,val):
    N = Maillon(val,p = M.precedent, s = M)
    
def inserer_avant_en_liste(L,it,val):
    inserer_avant(it._list_iterator__M,val)
    L._Liste__N += 1
    
Liste.insert = inserer_avant_en_liste

Suppression d'un maillon M¶

relier M.precedent et M.suivant
- M.precedent.suivant = M.suivant
- M.suivant.precedent = M.precedent
selon le langage, détruire M

In [11]:

def supprimer(M):
    assert(M and M.precedent and M.suivant)
    M.precedent.suivant = M.suivant
    M.suivant.precedent = M.precedent
    
def supprimer_en_liste(L,it):
    supprimer(it._list_iterator__M)
    L._Liste__N -= 1

Liste.erase = supprimer_en_liste

Opérations en tête¶

Elles peuvent être écrites en une ligne en utilisant les insertions et suppressions quelconques en lui donnant L.begin() en paramètre

In [12]:

def inserer_en_tete(L,val):
    L.insert(L.begin(),val)  
    
Liste.push_front = inserer_en_tete

In [13]:

def supprimer_en_tete(L):
    if L.empty(): raise IndexError()
    L.erase(L.begin())
    
Liste.pop_front = supprimer_en_tete

Testons leurs effets

In [14]:

L = Liste(); print(L)
for i in range(3):
    L.push_front(i**2); print(L)

⌀
⌀ ← 0 → ⌀
⌀ ← 1 ⇄ 0 → ⌀
⌀ ← 4 ⇄ 1 ⇄ 0 → ⌀

In [15]:

for i in range(4):
    L.pop_front(); print(L)

⌀ ← 1 ⇄ 0 → ⌀
⌀ ← 0 → ⌀
⌀

--------------------
IndexErrorTraceback (most recent call last)
<ipython-input-15-90ff2e20060f> in <module>()
      1 for i in range(4):
----> 2     L.pop_front(); print(L)

<ipython-input-13-cf6441071455> in supprimer_en_tete(L)
      1 def supprimer_en_tete(L):
----> 2     if L.empty(): raise IndexError()
      3     L.erase(L.begin())
      4 
      5 Liste.pop_front = supprimer_en_tete

IndexError:

Opérations en queue¶

Elles peuvent être écrites en une ligne en utilisant les insertions et suppressions quelconques. On insère devant L.end() et on supprime le maillon précédent L.end()

In [16]:

def inserer_en_queue(L,val):
    L.insert(L.end(),val)
    
Liste.push_back = inserer_en_queue

In [17]:

def supprimer_en_queue(L):
    if L.empty(): raise IndexError()
    L.erase(L.end().precedent())
    
Liste.pop_back = supprimer_en_queue

Testons leurs effets

In [18]:

L = Liste(); print(L)
for i in range(3):
    L.push_back(i*2)
    print(L)

⌀
⌀ ← 0 → ⌀
⌀ ← 0 ⇄ 2 → ⌀
⌀ ← 0 ⇄ 2 ⇄ 4 → ⌀

In [19]:

for i in range(4):
    L.pop_back()
    print(L)

⌀ ← 0 ⇄ 2 → ⌀
⌀ ← 0 → ⌀
⌀

--------------------
IndexErrorTraceback (most recent call last)
<ipython-input-19-6f68728ecf5d> in <module>()
      1 for i in range(4):
----> 2     L.pop_back()
      3     print(L)

<ipython-input-17-93f6b9477d3f> in supprimer_en_queue(L)
      1 def supprimer_en_queue(L):
----> 2     if L.empty(): raise IndexError()
      3     L.erase(L.end().precedent())
      4 
      5 Liste.pop_back = supprimer_en_queue

IndexError:

Itérer¶

Nous avons fourni plus tôt les fonctions d'itération standards. La principale nouveauté est l'apparition d'une méthode precedent qui permet de se déplacer de droite à gauche. Voyons quelques exemples d'utilisation

In [20]:

def afficher_liste(L):
    it = L.begin()
    while it != L.end():
        print(it, end="")
        if it.suivant() != L.end(): 
            print(end = " ⇄ ")
        it.incr()

In [21]:

T = [ 1, 3, 5, 7, 9, 11 ]; L = Liste()
for t in T: L.push_back(t)

afficher_liste(L)

1 ⇄ 3 ⇄ 5 ⇄ 7 ⇄ 9 ⇄ 11

In [22]:

def supprimer_decroissances(L):
    it = L.begin(); max_val = it.get_val()
    it = it.suivant()
    
    while it != L.end():
        if it.get_val() < max_val:
            tmp = it.suivant()
            L.erase(it); 
            it = tmp
        else:
            max_val = it.get_val()
            it.incr()

In [23]:

T = [ 1, 2, 3, 3, 2, 1, 2, 3, 4, 5, 6, 5, 4, 5, 6, 7, 8 ]; 
L = Liste()
for t in T: L.push_back(t)

supprimer_decroissances(L); print(L)

⌀ ← 1 ⇄ 2 ⇄ 3 ⇄ 3 ⇄ 3 ⇄ 4 ⇄ 5 ⇄ 6 ⇄ 6 ⇄ 7 ⇄ 8 → ⌀

In [24]:

def tri_par_insertion(L):
    if L.size() < 2: return
    
    k = L.begin().suivant()
    while k != L.end():
        tmp = k.get_val()
        
        j = k; i = j.precedent()
        while j != L.begin() and tmp < i.get_val():
            j.set_val(i.get_val())
            j = i.copie() 
            i.decr()
            
        j.set_val(tmp)
        k.incr()

In [25]:

T = [ 4, 2, 7, 5, 6, 9, 1, 3, 8 ]; L = Liste()
for t in T: L.push_back(t)

tri_par_insertion(L); print(L)

⌀ ← 1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5 ⇄ 6 ⇄ 7 ⇄ 8 ⇄ 9 → ⌀

Conclusions¶

Une liste doublement chainée utilise comme maillons des structures stockant individuellement

un élément
un lien vers l'élément suivant
un lien vers l'élément précédent

Les opérations efficaces en Θ(1) sont

insertion et suppression en tête et en queue
insertion et suppression en une position connue

Il n'y a ni pas d'accès indexé.

L'utilisation d'un maillon vide qui boucle la liste en tête et en queue - ainsi que celle d'itérateurs - simplifie la mise en oeuvre et l'utilisation de la structure.

ASD1 Notebooks on GitHub.io